// 用两个栈实现一个队列

// 实现的思想是：
/*      队列insert：栈S1入栈
 *      队列delete：首先判断栈S2是不是为空，若不为空，S2出栈即为队列delete元素
 *      若S2为空，则将S1中元素出栈，同时将出栈元素对S2入栈，S2栈顶元素即为队列delete元素
 *      */

#include <iostream>
#include <stack>

template <typename T>
class CQueue{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node);
    T deleteHead();

private:
    std::stack<T> stack1;
    std::stack<T> stack2;
};

template <typename T>
CQueue<T>::CQueue() {
    std::cout << "object is being created" << std::endl;
}

template <typename T>
CQueue<T>::~CQueue() {
    std::cout << "object is being deleted" << std::endl;
}

template <typename T>
void CQueue<T>::appendTail(const T &node) {
    stack1.push(node);
}

template <typename T>
T CQueue<T>::deleteHead() {
    if(stack2.empty()){
        if(stack1.empty()){
            throw "underflow";
        }else{
            for(int i=0; i<stack1.size(); i++){
                T t = stack1.top();
                stack1.pop();
                stack2.push(t);
            }
        }
    }
    T rt = stack2.top();
    stack2.pop();
    return rt;
}

int main() {
    CQueue<int> ex;
    try {
        ex.appendTail(1);
        ex.appendTail(5);
        std::cout << ex.deleteHead() << std::endl;
        ex.appendTail(8);
        std::cout << ex.deleteHead() << std::endl;
    }catch(const char* msg){
        std::cout << msg << std::endl;
    }

    return 0;
}

